package algo.utilitaire;

import algo.graphe.Graphe;
import algo.graphe.Noeud;
import java.util.LinkedList;
import java.util.NoSuchElementException;

/**
 * Outils permettant d'executer faire tout les calculs nécessaire pour l'algorithme de Moore
 * @author <a href="mailto:christian.dramsy@gmail.com">DRAMSY Christian</a>
 */
public class UtilitaireMoore {

    /**
     * Execute l'algorithme de Moore V1(avec les Tableau)
     * @param start Le sommet de depart
     * @param graphe 
     */
    public static void MooreTableau(int start, Graphe graphe, boolean displayResult) {
        if (!graphe.isConnexe()) {
            System.out.println("Le graphe doit être connexe");
            return;
        }

        //  C l'ensemble des noeud déjà visité
        boolean[] visited = new boolean[graphe.getOrdre()];
        for (int i = 0; i < graphe.getOrdre(); i++) {
            visited[i] = false;
        }
        int ordre = graphe.getOrdre();
        //  Le cout du chemin de beginNode au node autres sommet(indice du tableau)->correcpond au d(i) dans le sujet
        int[] distance = new int[ordre];
        //  Tableau contenant l'antecedant d'un sommet
        int[] antecedant = new int[ordre];
        //  On initialise toute les distances à INFINI et ls antecedant à -1
        for (int i = 0; i < ordre; i++) {
            antecedant[i] = -1;
            distance[i] = Integer.MAX_VALUE;
        }
        int pivot = start;
        // C = 1
        visited[pivot] = true;

        //  d(1) = 0 , d(i) = infini pour tout i != 1
        distance[pivot] = 0;

        //  Matrice qui verifie les noeud de provenance d'un noeud. si 3 est successeur de 0 alors from[3][0] = true;
        boolean[][] from = new boolean[ordre][ordre];

        for (int i = 0; i < ordre; i++) {
            for (int j = 0; j < ordre; j++) {
                from[i][j] = false;
            }
        }

        //  recuperation des successeurs
        boolean[] isSuccesseurs = graphe.successeurs(pivot);
        //  Pout tout sommets x non visité
        for (int x = 0; x < ordre; x++) {
            if (!visited[x]) {
                if (isSuccesseurs[x]) {
                    distance[x] = graphe.getMatriceAdjValue(pivot, x);
                    antecedant[x] = pivot;
                    from[x][pivot] = true;

                } else {
                    distance[x] = Integer.MAX_VALUE;
                }
            }
        }

        boolean allNodeVisited = false;
        while (true) {
            allNodeVisited = true;
            //  verification si tout les noeuds ont été visité
            for (int i = 0; i < ordre; i++) {
                if (visited[i] == false) {
                    allNodeVisited = false;
                    break;
                }
            }
            if (allNodeVisited) {
                break;
            }

            int min = Integer.MAX_VALUE;
            int y = -1;
            for (int i = 0; i < ordre; i++) {
                if (!visited[i] && min > distance[i]) {
                    min = distance[i];
                    y = i;
                }
            }

            pivot = y;
            if (pivot == -1) {
                break;
            }
            visited[pivot] = true;

            //  recuperation des successeurs
            isSuccesseurs = graphe.successeurs(pivot);

            //  Pout tout sommets x non visité
            for (int x = 0; x < ordre; x++) {
                //  si c'est un successeur de pivot ET QUE CE N'EST PAS SON PERE
                if (x != pivot && from[pivot][x] == false && isSuccesseurs[x]) {
                    if (distance[pivot] + graphe.getMatriceAdjValue(pivot, x) < distance[x]) {
                        distance[x] = distance[pivot] + graphe.getMatriceAdjValue(pivot, x);
                        antecedant[x] = pivot;
                        from[x][pivot] = true;
                        visited[x] = false;
                    }
                }
            }
        }
        if (displayResult) {
            UtilitaireAffichage.afficherResultatDijkstra(distance, antecedant, start);
        }
    }

    public static void executeMooreTableau(Graphe graphe, boolean displayResult) {
        if (!graphe.isConnexe()) {
            System.out.println("Le graphe doit être connexe");
            return;
        }
        for (int i = 0; i < graphe.getOrdre(); i++) {
            UtilitaireMoore.MooreTableau(i, graphe, displayResult);
        }
    }

    /**
     * Execute l'algorithme de Moore V1(avec les Liste)
     * @param start Le sommet de depart
     * @param graphe 
     */
    public static void MooreListe(int start, Graphe graphe, boolean displayResult) {
        if (!graphe.isConnexe()) {
            System.out.println("Le graphe doit être connexe");
            return;
        }

        //  C l'ensemble des noeud déjà visité
        boolean[] visited = new boolean[graphe.getOrdre()];
        for (int i = 0; i < graphe.getOrdre(); i++) {
            visited[i] = false;
        }
        int ordre = graphe.getOrdre();
        //  Le cout du chemin de beginNode au node autres sommet(indice du Liste)->correcpond au d(i) dans le sujet
        int[] distance = new int[ordre];
        //  Liste contenant l'antecedant d'un sommet
        int[] antecedant = new int[ordre];
        //  On initialise toute les distances à INFINI et ls antecedant à -1
        for (int i = 0; i < ordre; i++) {
            antecedant[i] = -1;
            distance[i] = Integer.MAX_VALUE;
        }
        int pivot = start;
        // C = 1
        visited[pivot] = true;

        //  d(1) = 0 , d(i) = infini pour tout i != 1
        distance[pivot] = 0;

        //  Matrice qui verifie les noeud de provenance d'un noeud. si 3 est successeur de 0 alors from[3][0] = true;
        boolean[][] from = new boolean[ordre][ordre];

        for (int i = 0; i < ordre; i++) {
            for (int j = 0; j < ordre; j++) {
                from[i][j] = false;
            }
        }

        //  recuperation des successeurs
        boolean[] isSuccesseurs = graphe.successeurs(pivot);
        //  Pout tout sommets x non visité
        for (int x = 0; x < ordre; x++) {
            if (!visited[x]) {
                if (isSuccesseurs[x]) {
                    distance[x] = graphe.getMatriceAdjValue(pivot, x);
                    antecedant[x] = pivot;
                    from[x][pivot] = true;

                } else {
                    distance[x] = Integer.MAX_VALUE;
                }
            }
        }

        boolean allNodeVisited = false;
        while (true) {
            allNodeVisited = true;
            //  verification si tout les noeuds ont été visité
            for (int i = 0; i < ordre; i++) {
                if (visited[i] == false) {
                    allNodeVisited = false;
                    break;
                }
            }
            if (allNodeVisited) {
                break;
            }

            int min = Integer.MAX_VALUE;
            int y = -1;
            LinkedList<Noeud> list = graphe.creerStructureListeChainee().get(pivot);
            Noeud tmp;
            while (true) {
                try {
                    tmp = list.removeFirst();
                    if (!visited[tmp.getNum()] && min > distance[tmp.getNum()]) {
                        min = distance[tmp.getNum()];
                        y = tmp.getNum();
                    }
                } catch (NoSuchElementException e) {
                    break;
                }
            }

            pivot = y;
            if (pivot == -1) {
                break;
            }
            visited[pivot] = true;
            //  recuperation des successeurs
            isSuccesseurs = graphe.successeurs(pivot);

            //  Pout tout sommets x non visité
            for (int x = 0; x < ordre; x++) {
                //  si c'est un successeur de pivot ET QUE CE N'EST PAS SON PERE
                if (x != pivot && from[pivot][x] == false && isSuccesseurs[x]) {
                    if (distance[pivot] + graphe.getMatriceAdjValue(pivot, x) < distance[x]) {
                        distance[x] = distance[pivot] + graphe.getMatriceAdjValue(pivot, x);
                        antecedant[x] = pivot;
                        from[x][pivot] = true;
                        visited[x] = false;
                    }
                }
            }
        }

        if (displayResult) {
            UtilitaireAffichage.afficherResultatDijkstra(distance, antecedant, start);
        }
    }

    public static void executeMooreListe(Graphe graphe, boolean displayResult) {
        if (!graphe.isConnexe()) {
            System.out.println("Le graphe doit être connexe");
            return;
        }
        for (int i = 0; i < graphe.getOrdre(); i++) {
            UtilitaireMoore.MooreListe(i, graphe, displayResult);
        }
    }

    /**
     * Execute l'algorithme de Moore V1(avec les Tableau)
     * @param start Le sommet de depart
     * @param graphe 
     */
    public static void MooreTas(int start, Graphe graphe, boolean displayResult) {
        if (!graphe.isConnexe()) {
            System.out.println("Le graphe doit être connexe");
            return;
        }

        //  C l'ensemble des noeud déjà visité
        boolean[] visited = new boolean[graphe.getOrdre()];
        for (int i = 0; i < graphe.getOrdre(); i++) {
            visited[i] = false;
        }
        int ordre = graphe.getOrdre();
        //  Le cout du chemin de beginNode au node autres sommet(indice du tableau)->correcpond au d(i) dans le sujet
        int[] distance = new int[ordre];
        //  Tableau contenant l'antecedant d'un sommet
        int[] antecedant = new int[ordre];
        //  On initialise toute les distances à INFINI et ls antecedant à -1
        for (int i = 0; i < ordre; i++) {
            antecedant[i] = -1;
            distance[i] = Integer.MAX_VALUE;
        }
        // C = 1
        visited[start] = true;

        //  d(1) = 0 , d(i) = infini pour tout i != 1
        distance[start] = 0;

        //  Matrice qui verifie les noeud de provenance d'un noeud. si 3 est successeur de 0 alors from[3][0] = true;
        boolean[][] from = new boolean[ordre][ordre];

        for (int i = 0; i < ordre; i++) {
            for (int j = 0; j < ordre; j++) {
                from[i][j] = false;
            }
        }

        //  Le tas pour le traitement
        Noeud[] tas = new Noeud[0];
        Noeud pivot = new Noeud(start, 0);

        //  recuperation des successeurs
        boolean[] isSuccesseurs = graphe.successeurs(start);
        //  Pout tout sommets x non visité
        for (int x = 0; x < ordre; x++) {
            if (!visited[x]) {
                if (isSuccesseurs[x]) {
                    distance[x] = graphe.getMatriceAdjValue(pivot.getNum(), x);
                    antecedant[x] = pivot.getNum();
                    from[x][pivot.getNum()] = true;
                    if (!visited[x]) {
                        tas = UtilitaireTas.ajouter(tas, new Noeud(x, distance[x]));
                    }
                } else {
                    distance[x] = Integer.MAX_VALUE;
                }
            }
        }

        boolean allNodeVisited = false;
        while (true) {
            allNodeVisited = true;
            //  verification si tout les noeuds ont été visité
            for (int i = 0; i < ordre; i++) {
                if (visited[i] == false) {
                    allNodeVisited = false;
                    break;
                }
            }
            if (allNodeVisited) {
                break;
            }

            try {
                pivot = tas[0];
                visited[pivot.getNum()] = true;
            } catch (ArrayIndexOutOfBoundsException ex) {
                break;
            }
            tas = UtilitaireTas.suppressionRacine(tas);
            //  recuperation des successeurs
            isSuccesseurs = graphe.successeurs(pivot.getNum());

            //  Pout tout sommets x non visité
            for (int x = 0; x < ordre; x++) {
                //  si c'est un successeur de pivot ET QUE CE N'EST PAS SON PERE
                if (x != pivot.getNum() && from[pivot.getNum()][x] == false && isSuccesseurs[x]) {
                    if (distance[pivot.getNum()] + graphe.getMatriceAdjValue(pivot.getNum(), x) < distance[x]) {
                        distance[x] = distance[pivot.getNum()] + graphe.getMatriceAdjValue(pivot.getNum(), x);
                        antecedant[x] = pivot.getNum();
                        from[x][pivot.getNum()] = true;
                        visited[x] = false;
                        if (!visited[x]) {
                            tas = UtilitaireTas.ajouter(tas, new Noeud(x, distance[x]));
                        }
                    }
                }
            }
        }
        if (displayResult) {
            UtilitaireAffichage.afficherResultatDijkstra(distance, antecedant, start);
        }
    }

    public static void executeMooreTas(Graphe graphe, boolean displayResult) {
        if (!graphe.isConnexe()) {
            System.out.println("Le graphe doit être connexe");
            return;
        }
        for (int i = 0; i < graphe.getOrdre(); i++) {
            UtilitaireMoore.MooreTas(i, graphe, displayResult);
        }
    }
}
